package org.eoti.math.cf;

import org.eoti.math.Fraction;

import java.math.BigInteger;
import java.util.Iterator;

/*
 * The MIT License
 *
 * Copyright (c) 2009 Malachi de AElfweald <malachid@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * Based on http://malsmath.blogspot.com/2009/02/continued-fractions.html
 */

public abstract class ContinuedFraction
implements Comparable<ContinuedFraction>
{
	private final static BigInteger one = BigInteger.ONE;
	private final static BigInteger zero = BigInteger.ZERO;
	protected ContinuedFraction()
	{
	}

	public MobiusCF add(ContinuedFraction other)
	{
		return new MobiusCF(
				"(%s + %s)",
				this, other,
				zero, one, one, zero,
		    zero, zero, zero, one
		);
	}

	public MobiusCF subtract(ContinuedFraction other)
	{
		return new MobiusCF(
				"(%s - %s)",
				this, other,
				zero, one, one.negate(), zero,
		    zero, zero, zero, one
		);
	}

	public MobiusCF multiply(ContinuedFraction other)
	{
		return new MobiusCF(
				"(%s * %s)",
				this, other,
				one, zero, zero, zero,
		    zero, zero, zero, one
		);
	}

	public MobiusCF divide(ContinuedFraction other)
	{
		return new MobiusCF(
				"(%s / %s)",
				this, other,
				zero, one, zero, zero,
		    zero, zero, one, zero
		);
	}

	public NegateCF negate(){return new NegateCF(this);}
	public InvertCF invert(){return new InvertCF(this);}
	
	public abstract BigInteger getNumerator(BigInteger index);
	public abstract BigInteger getDenominator(BigInteger index);

	/**
	 * Compares this object with the specified object for order.  Returns a negative integer, zero, or a positive integer
	 * as this object is less than, equal to, or greater than the specified object.
	 * <p/>
	 * <p>The implementor must ensure <tt>sgn(x.compareTo(y)) == -sgn(y.compareTo(x))</tt> for all <tt>x</tt> and
	 * <tt>y</tt>.  (This implies that <tt>x.compareTo(y)</tt> must throw an exception iff <tt>y.compareTo(x)</tt> throws
	 * an exception.)
	 * <p/>
	 * <p>The implementor must also ensure that the relation is transitive: <tt>(x.compareTo(y)&gt;0 &amp;&amp;
	 * y.compareTo(z)&gt;0)</tt> implies <tt>x.compareTo(z)&gt;0</tt>.
	 * <p/>
	 * <p>Finally, the implementor must ensure that <tt>x.compareTo(y)==0</tt> implies that <tt>sgn(x.compareTo(z)) ==
	 * sgn(y.compareTo(z))</tt>, for all <tt>z</tt>.
	 * <p/>
	 * <p>It is strongly recommended, but <i>not</i> strictly required that <tt>(x.compareTo(y)==0) == (x.equals(y))</tt>.
	 * Generally speaking, any class that implements the <tt>Comparable</tt> interface and violates this condition should
	 * clearly indicate this fact.  The recommended language is "Note: this class has a natural ordering that is
	 * inconsistent with equals."
	 * <p/>
	 * <p>In the foregoing description, the notation <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical
	 * <i>signum</i> function, which is defined to return one of <tt>-1</tt>, <tt>0</tt>, or <tt>1</tt> according to
	 * whether the value of <i>expression</i> is negative, zero or positive.
	 *
	 * @param cf the continued fraction to be compared.
	 *
	 * @return a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the
	 *         specified object.
	 *
	 * @throws NullPointerException if the specified object is null
	 * @throws ClassCastException   if the specified object's type prevents it from being compared to this object.
	 */
	public int compareTo( ContinuedFraction cf ){
		Iterator<Fraction> us = getValues().iterator();
		Iterator<Fraction> them = cf.getValues().iterator();
		while(us.hasNext() && them.hasNext())
		{
			Fraction ours = us.next();
			Fraction theirs = them.next();
			if(ours == null)
			{
				if(theirs == null) return 0;
				return -1;
			}else if(theirs == null){
				return 1;
			}
			int comparison = ours.compareTo(theirs);
			if(comparison != 0) return comparison;
		}
		if(us.hasNext()) return 1;
		if(them.hasNext()) return -1;
		return 0;
	}

	public String toString()
	{
		return getClass().getSimpleName();
	}

	public Iterable<Fraction> getValues()
	{
		return new Iterable<Fraction>()
		{

			/**
			 * Returns an iterator over a set of elements of type T.
			 *
			 * @return an Iterator.
			 */
			public Iterator<Fraction> iterator(){
				return new ValueIterator();
			}
		};
	}

	public Iterable<Fraction> getConvergents()
	{
		return new Iterable<Fraction>()
		{

			/**
			 * Returns an iterator over a set of elements of type T.
			 *
			 * @return an Iterator.
			 */
			public Iterator<Fraction> iterator(){
				return new ConvergentIterator(ContinuedFraction.this);
			}
		};
	}

	class ValueIterator
	implements Iterator<Fraction>
	{
		BigInteger index = zero;

		public ValueIterator()
		{

		}

		/**
		 * Returns {@code true} if the iteration has more elements. (In other words, returns {@code true} if {@link #next}
		 * would return an element rather than throwing an exception.)
		 *
		 * @return {@code true} if the iteration has more elements
		 */
		public boolean hasNext(){
			if(getDenominator( index ) == null) return false;

			if(getNumerator(index) == null)
			{
				if(index.equals(zero)) return true;
				return false;
			}

			return true;
		}

		/**
		 * Returns the next element in the iteration.
		 *
		 * @return the next element in the iteration
		 *
		 * @throws java.util.NoSuchElementException
		 *          if the iteration has no more elements
		 */
		public Fraction next(){
			BigInteger den = getDenominator(index);
			BigInteger num = getNumerator(index);
			index = index.add(one);
			return new Fraction(num, den);
		}

		/**
		 * Removes from the underlying collection the last element returned by this iterator (optional operation).  This method
		 * can be called only once per call to {@link #next}.  The behavior of an iterator is unspecified if the underlying
		 * collection is modified while the iteration is in progress in any way other than by calling this method.
		 *
		 * @throws UnsupportedOperationException if the {@code remove} operation is not supported by this iterator
		 * @throws IllegalStateException         if the {@code next} method has not yet been called, or the {@code remove}
		 *                                       method has already been called after the last call to the {@code next} method
		 */
		public void remove(){
			throw new UnsupportedOperationException("remove is not supported");
		}
	}
}
